//************************************************************
//    > File Name: heap_srot.c
//    > Author: davis
//    > Mail:  
//    > Created Time: 2017年03月15日  9:42:24
//***********************************************************

#include<stdio.h>
void heap_adjust(int *a,int p,int n){
	for(int maxid=p, tmp;p<(n>>1); p=maxid){
		if((p<<1)+1<n && a[(p<<1)+1]>a[maxid])
			maxid=(p<<1)+1;
		if((p<<1)+2<n && a[(p<<1)+2]>a[maxid])
			maxid=(p<<1)+2;
		if(maxid==p) break;
		tmp=a[maxid];
		a[maxid]=a[p];
		a[p]=tmp;
	}
}
void heap_adjust2(int *a,int p,int n){
	while(p<(n>>1)){
		int maxid=p,tmp;
		if((p<<1)+1<n && a[(p<<1)+1]>a[maxid])
			maxid=(p<<1)+1;
		if((p<<1)+2<n && a[(p<<1)+2]>a[maxid])
			maxid=(p<<1)+2;
		if(maxid==p) break;
		tmp=a[maxid];
		a[maxid]=a[p];
		a[p]=tmp;
		p=maxid;
	}
}
//from buttom to top  heap_adjust1 heap_adjust2
void heap_sort(int *a,int n){
	for(int i=(n>>1)-1;i>-1;heap_adjust2(a,i--,n));
	for(int i=n-1,temp;i>0;--i){
		temp=a[i];
		a[i]=a[0];
		a[0]=temp;
		heap_adjust2(a,0,i);
	}
}

void heap_adjust3(int *a,int c){
	int p=(c-1)>>1,temp;
	for(;p>-1 && c && a[p]<a[c];c=p,p=(c-1)>>1){
		temp=a[p];
		a[p]=a[c];
		a[c]=temp;
	}
}
//from top to buttom can not sort
void heap_sort2(int *a,int n){
	for(int i=1;i<n;heap_adjust3(a,i++));
}
int main()
{
	int a[]={3,6,2,5,7,1,2,10,3,4,9};
	for(int i=0;i<sizeof(a)/sizeof(a[0]);i++)
		printf("%d ",a[i]);
	printf("\n");
	heap_sort(a,sizeof(a)/sizeof(a[0]));
	for(int i=0;i<sizeof(a)/sizeof(a[0]);i++)
		printf("%d ",a[i]);
	return 0;
}
